#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <queue>

const int N = 400005;
int v, p, n, m, tot, cnt, mind[N << 1], fa[N << 1], wei[N << 1], f[21][N << 1], dis[N];

inline int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

inline int read() {
  int x = 0, ch = getchar(), flag = 0;
  while (!isdigit(ch)) {
    if (ch == '-') flag = 1;
    ch = getchar();
  }
  while (isdigit(ch)) x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
  return flag ? -x : x;
}

int e_cnt, g_cnt, h_cnt, eheads[N << 1], hheads[N];

struct Edge {
  int v, nxt, w, c;
  inline bool operator<(const Edge &rhs) const { return w > rhs.w; }
} e[N], g[N], h[N << 1];

inline void add(int u, int v) { e[++e_cnt].v = v, e[e_cnt].nxt = eheads[u], eheads[u] = e_cnt; }

inline void add(int u, int v, int l) {
  h[++h_cnt].v = v, h[h_cnt].nxt = hheads[u], hheads[u] = h_cnt, h[h_cnt].c = l;
}

inline void add(int u, int v, int c, int w) {
  g[++g_cnt].nxt = u, g[g_cnt].v = v, g[g_cnt].w = w, g[g_cnt].c = c;
}

inline int solve(int x) {
  for (int i = 19; ~i; --i)
    if (f[i][x] && wei[f[i][x]] > p) x = f[i][x];
  return mind[x];
}

void dfs(int x) {
  if (!eheads[x]) {
    mind[x] = dis[x];
    return;
  }
  for (int i = eheads[x]; i; i = e[i].nxt) {
    dfs(e[i].v);
    mind[x] = std::min(mind[x], mind[e[i].v]);
  }
}

inline void init() {
  memset(eheads, 0, sizeof(eheads));
  memset(hheads, 0, sizeof(hheads));
  memset(dis, 0x3f, sizeof(dis));
  memset(mind, 0x3f, sizeof(mind));
  for (int i = 1; i <= n << 1; ++i) {
    fa[i] = i;
  }
  tot = n;
  e_cnt = g_cnt = h_cnt = 0;
}

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("testdata.in", "r", stdin);
  freopen("testdata.out", "w", stdout);
#endif
#ifndef LOCAL
  freopen("P4768[NOI2018]Trip(KruskalTree).in", "r", stdin);
  freopen("P4768[NOI2018]Trip(KruskalTree).out", "w", stdout);
#endif
#endif

  int T = read();
  while (T--) {
    n = read(), m = read();
    init();
    int u, v, l, a;
    for (int i = 1; i <= m; ++i) {
      scanf("%d%d%d%d", &u, &v, &l, &a);
      add(u, v, l, a);
      add(u, v, l);
      add(v, u, l);
    }
    dis[1] = 0;
    std::priority_queue<std::pair<int, int> > pq;
    pq.push(std::make_pair(0, 1));
    while (!pq.empty()) {
      int u = pq.top().second, d = -pq.top().first;
      pq.pop();
      if (dis[u] == d)
        for (int i = hheads[u]; i; i = h[i].nxt) {
          int v = h[i].v;
          if (dis[v] > d + h[i].c) {
            dis[v] = d + h[i].c;
            pq.push(std::make_pair(-dis[v], v));
          }
        }
    }
    std::sort(g + 1, g + g_cnt + 1);
    for (int i = 1; i <= g_cnt; i++) {
      int ffu = find(g[i].nxt), ffv = find(g[i].v);
      if (ffu != ffv) {
        add(++tot, ffu);
        add(tot, ffv);
        fa[ffu] = tot;
        fa[ffv] = tot;
        f[0][ffu] = f[0][ffv] = tot;
        wei[tot] = g[i].w;
      }
    }
    dfs(tot);
    for (int i = 1; i < 20; ++i) {
      for (int j = 1; j <= tot; ++j) {
        f[i][j] = f[i - 1][f[i - 1][j]];
      }
    }
    int ans = 0, q, k, s;
    q = read(), k = read(), s = read();
    while (q--) {
      v = read(), p = read();
      v = (v + ans * k - 1) % n + 1;
      p = (p + ans * k) % (s + 1);
      printf("%d\n", ans = solve(v));
    }
  }
  return 0;
}